#if 0

#include <iostream>

using namespace std;


uint64_t fibno(uint64_t n)
{

    if (n < 0)
    {
        cout << "Input number can not less than 0!" << endl;
        exit(0);
    }

    if ( n <= 1)
    {
        return n;
    }

    static uint64_t a = 0;
    static uint64_t b = 1;
    cout << "n: " << n <<endl;
    for (uint64_t i = 2;i <= n;i++)
    {
        cout << "a: " << a << " b: " << b << endl;
        uint64_t temp = a+b;
        a = b;
        b = temp;
        
    }

    return b;
}



int main()
{


    cout << "输入样例: " << endl;

    uint64_t a[10] = {0};
    uint64_t idx = 0;

    while(1)
    {
        cin >> a[idx];
        if (a[idx] == -1)
        {
            break;
        }
        idx++;
    }

    cout << "输出样例: " << endl;
    for (uint64_t i = 0;i < idx;i++)
    {
        cout << (fibno(a[i]) % 10000) << endl;
        // cout << fibonacci_com_no(a[i]) << endl;
    }

    return 0;
}


#else


#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int mod = 10000;

int n;

void mul(int f[2], int a[2][2]) //f = f * a
{
    int c[2] = {0};

    for(int j = 0; j < 2; j++)
        for(int k = 0; k < 2; k++)
            c[j] = (c[j] + (LL)f[k] * a[k][j]) % mod;
    memcpy(f, c, sizeof c);
}

void mulself(int a[2][2]) //a = a * a
{
    int c[2][2] = {0};

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + (LL)a[i][k] * a[k][j]) % mod;
    memcpy(a, c, sizeof c);
}

int main()
{
    while(scanf("%d", &n), n != -1)
    {
        //初始化矩阵
        int f[2] = {0, 1}; //斐波那契矩阵
        int a[2][2] = {{0, 1}, {1, 1}}; //A 矩阵

        //快速幂计算 f * A^n
        while(n)
        {
            if(n & 1) mul(f, a);
            mulself(a);
            n >>= 1;
        }

        printf("%d\n", f[0]);
    }
    return 0;
}

#endif